package com.ifish.leetcode.problem.algorithm;

import com.ifish.leetcode.problem.BaseLeetCodeProblem;

/**
 * Created by iFish on 2017/7/8.
 */

public class _0002 extends BaseLeetCodeProblem {

    @Override
    public String title() {
        return "Add Two Numbers";
    }

    @Override
    public int difficulty() {
        return 1;
    }

    @Override
    public void run() {
        super.run();
        ListNode l1 = new ListNode(new int[]{2,4,3});
        ListNode l2 = new ListNode(new int[]{5,6,4});

        ListNode addl = addTwoNumbers(l1, l2);
        addl.print();
    }

    public static class ListNode {
        int val;
        ListNode next;
        public ListNode(int x) {
            val = x;
        }

        public ListNode(int []xs) {
            ListNode l = this;
            for (int i = 0; i < xs.length; i++) {
                if (i > 0) {
                    l.next = new ListNode(xs[i]);
                    l = l.next;
                } else {
                    l.val = xs[i];
                }
            }
        }

        public void print() {
            ListNode l = this;
            do {
                if (l.next == null) {
                    System.out.print(l.val + "");
                } else {
                    System.out.print(l.val + "->");
                }
                l = l.next;
            } while (l != null);
            System.out.println();
        }
    }

    int add, carry = 0;
    ListNode curl = new ListNode(-1);

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        curl.val = -1;
        ListNode l = new ListNode(-1);
        while (l1 != null || l2 != null || carry != 0) {
            if (carry != 0 && l1 == null && l2 == null) {
                setNode(l, carry);
                carry = 0;
            } else if (l1 == null) {
                addDigits(l2.val, 0);
                setNode(l, add);
                l2 = l2.next;
            } else if (l2 == null) {
                addDigits(l1.val, 0);
                setNode(l, add);
                l1 = l1.next;
            } else {
                addDigits(l1.val, l2.val);
                setNode(l, add);
                l1 = l1.next;
                l2 = l2.next;
            }
        }
        add = 0;
        carry = 0;
        return l;
    }

    private void setNode(ListNode l, int x) {
        if (l.val == -1) {
            l.val = x;
        } else if (curl.val == -1) {
            curl.val = x;
            l.next = curl;
        } else {
            curl.next = new ListNode(x);
            curl = curl.next;
        }
    }

    private void addDigits(int a, int b) {
        add = a + b + carry;
        if (add >= 10) {
            add -= 10;
            carry = 1;
        } else {
            carry = 0;
        }
    }
}
